package com.zjsru.plan2024.oneday;

import java.util.*;

/**
 * 721. 账户合并
 * @Author: cookLee
 * @Date: 2024-07-15
 */
public class AccountsMerge {

    /**
     * 主
     * \
     * 输入：accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
     * 输出：[["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
     * 解释：
     * 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
     * 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
     * 可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
     * ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
     * \
     * 输入：accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
     * 输出：[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]
     * \
     * @param args args
     */
    public static void main(String[] args) {
        AccountsMerge accountsMerge = new AccountsMerge();
        List<List<String>> accounts = new ArrayList<>();
        List<String> account1 = Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com");
        List<String> account2 = Arrays.asList("John", "johnnybravo@mail.com");
        List<String> account3 = Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com");
        List<String> account4 = Arrays.asList("Mary", "mary@mail.com");
        accounts.add(account1);
        accounts.add(account2);
        accounts.add(account3);
        accounts.add(account4);
        System.out.println(accountsMerge.accountsMerge(accounts));
    }


    /**
     * 帐户合并：哈希表+DFS
     *
     * @param accounts 账目
     * @return {@link List}<{@link List}<{@link String}>>
     */
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        //把 accounts 中的信息提取到哈希表 emailToIds 中，key 为邮箱地址，value 为这个邮箱对应的账户下标列表。
        Map<String,List<Integer>> emailToIds = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts.get(i).size() ; j++) {
                emailToIds.computeIfAbsent(accounts.get(i).get(j),x -> new ArrayList<>()).add(i);
            }
        }

        List<List<String >> ans = new ArrayList<>();
        //初始化一个长为 n 的全为 false 的布尔数组 vis，用来标记访问过的账户下标。
        boolean[] vis = new boolean[accounts.size()];
        //在DFS遍历用到的邮件地址
        Set<String> emailAddress = new HashSet<>();
        for (int i = 0; i < accounts.size(); i++) {
            if(vis[i]){
                continue;
            }
            emailAddress.clear();
            this.dfs(i,accounts,emailToIds,vis,emailAddress);

            List<String> res = new ArrayList<>(emailAddress);
            Collections.sort(res);
            //在首位放入人名
            res.add(0,accounts.get(i).get(0));

            ans.add(res);
        }

        return ans;
    }

    /**
     * dfs
     *
     * @param i            我
     * @param accounts     账目
     * @param emailToIds   电子邮件至ids
     * @param vis          vis
     * @param emailAddress 电子邮件地址
     */
    private void dfs(int i, List<List<String>> accounts, Map<String, List<Integer>> emailToIds, boolean[] vis, Set<String> emailAddress) {
        vis[i] = true;
        for (int j = 1; j <accounts.get(i).size() ; j++) {
            String email = accounts.get(i).get(j);
            if (emailAddress.contains(email)) {
                continue;
            }
            emailAddress.add(email);
            // 遍历所有包含该邮箱地址的账户下标 index
            for (int index : emailToIds.get(email)) {
                //未访问过,index即是账户下标
                if (!vis[index]) {
                    this.dfs(index, accounts, emailToIds, vis, emailAddress);
                }
            }

        }
    }

}
